Stochastic Belief Propagation: A Low-Complexity Alternative to the Sum-Product Algorithm

摘要

The sum-product or belief propagation (BP) algorithm is a widely-usedmessage-passing algorithm for computing marginal distributions in graphicalmodels with discrete variables. At the core of the BP message updates, whenapplied to a graphical model with pairwise interactions, lies a matrix-vectorproduct with complexity that is quadratic in the state dimension $d$, andrequires transmission of a $(d-1)$-dimensional vector of real numbers(messages) to its neighbors. Since various applications involve very largestate dimensions, such computation and communication complexities can beprohibitively complex. In this paper, we propose a low-complexity variant ofBP, referred to as stochastic belief propagation (SBP). As suggested by thename, it is an adaptively randomized version of the BP message updates in whicheach node passes randomly chosen information to each of its neighbors. The SBPmessage updates reduce the computational complexity (per iteration) fromquadratic to linear in $d$, without assuming any particular structure of thepotentials, and also reduce the communication complexity significantly,requiring only $\log{d}$ bits transmission per edge. Moreover, we establish anumber of theoretical guarantees for the performance of SBP, showing that itconverges almost surely to the BP fixed point for any tree-structured graph,and for graphs with cycles satisfying a contractivity condition. In addition,for these graphical models, we provide non-asymptotic upper bounds on theconvergence rate, showing that the $\ell_{\infty}$ norm of the error vectordecays no slower than $O(1/\sqrt{t})$ with the number of iterations $t$ ontrees and the mean square error decays as $O(1/t)$ for general graphs. Theseanalysis show that SBP can provably yield reductions in computational andcommunication complexities for various classes of graphical models.